package cn.djb.day7;

import cn.djb.day6.TreeNode;

import java.util.*;

/**
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 */
class Solution_3 {


    public boolean isSymmetric2(TreeNode root) {
        if (null == root) return true;

        return recur(root.left, root.right);
    }

    private boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;

        if (L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }

    @Deprecated
    public boolean isSymmetric(TreeNode root) {
        if (null == root) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<TreeNode> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode pop = queue.poll();

                if ((pop.left != null && pop.right == null)
                        || (pop.left == null && pop.right != null)) return false;
                if (pop.left != null) {
                    queue.add(pop.left);
                    list.add(pop.left);
                }
                if (pop.right != null) {
                    queue.add(pop.right);
                    list.add(pop.right);
                }
            }
            int count = queue.size();

            if (count > 0 && count % 2 == 1) return false;

            for (int i = 0; i < count / 2; i++) {
                TreeNode leftNode = list.get(i);
                TreeNode rightNode = list.get(count - i - 1);
                if (leftNode.val != rightNode.val) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        TreeNode left = new TreeNode(2);
        left.left = new TreeNode(3);
        left.right = new TreeNode(4);

        TreeNode right = new TreeNode(2);
        right.left = new TreeNode(4);
        right.right = new TreeNode(3);

        root.left = left;
        root.right = right;
        Solution_3 solution_3 = new Solution_3();
        System.out.println(solution_3.isSymmetric(root));
    }


}